2168. Квадратный дырокол

Во время смены ЛКШ.Август.2009 были проведены испытания дырокола, который делает квадратные дырки. Бейджик имеет разметку n×m клеток, каждую из которых можно пробить дыроколом. На схеме 1 – пробитая клетка, 0 – не пробитая. Сколько маленьких бейджиков причудливой формы останется у ЛКШонка?

Вход. В первой строке даны размеры бейджика n и m (1 ≤ n, m ≤ 100). В последующих n строках дана схема проколотого бейджика.

Выход. Вывести количество полученных бейджиков.

Пример входа	Пример выхода
5 4 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0	3

РЕШЕНИЕ

поиск в глубину

Анализ алгоритма

После использования дырокола бейджик распадется на несколько частей, каждая из которых будет представлять собой набор стоящих рядом непробитых клеток. Таким образом в задаче следует найти количество компонент связности, задаваемых символами 0.

Пример

Полученные три бейджика отображены разными цветами:

Реализация алгоритма

Бейджик будем хранить в двумерном символьном массиве mas.

#define MAX 101

int mas[MAX][MAX];

Запускаем поиск в глубину из точки (i, j). Проверяем, что мы находимся в границах дырокола. Если в точке (i, j) клетка пробита, то завершаем поиск. Иначе помечаем клетку пройденной (например, пробиваем ее), и стараемся пойти влево в (i, j – 1), вправо в (i, j + 1), вверх в (i – 1, j) и вниз в (i + 1, j).

void dfs(int i, int j)

{

if ((i < 0) || (i >= n) || (j < 0) || (j >= m)) return;

if (mas[i][j] == 1) return;

mas[i][j] = 1;

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

Основная часть программы. Читаем лабиринт в двумерный символьный массив mas.

scanf("%d %d",&n,&m);

for(i = 0; i < n; i++)

for(j = 0; j < m; j++)

scanf("%d",&mas[i][j]);

В переменной res подсчитываем количество компонент связности.

res = 0;

for(i = 0; i < n; i++)

for(j = 0; j < m; j++)

if (mas[i][j] == 0)

{

dfs(i,j);

res++;

}

Выводим количество полученных бейджиков.

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

static int g[][], used[];

static int n, m;

static void dfs(int i, int j)

{

if ((i < 0) || (i >= n) || (j < 0) || (j >= m)) return;

if (g[i][j] == 1) return;

g[i][j] = 1;

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

n = con.nextInt();

m = con.nextInt();

g = new int[n][m];

used = new int[n];

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

g[i][j] = con.nextInt();

int res = 0;

for(int i = 0; i < n; i++)

for(int j = 0; j < m; j++)

if (g[i][j] == 0)

{

dfs(i,j);

res++;

}

System.out.print(res);

con.close();

}

}